class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        stack = []
        node = head
        while node:
            stack.append(node)
            node = node.next
        while len(stack) >= 2:
            top_node = stack[0]
            del stack[0]
            bottom_node = stack.pop()
            top_node.next = bottom_node
            if stack:
                bottom_node.next = stack[0]
            else:
                bottom_node.next = None
        if stack:
            stack[-1].next = None
